Polar codes are capacity achieving codes that have received much attention lately, and are being considered for specification as the channel codes in fifth generation (5G) communication systems. Currently, polar codes have been adopted for the control channel of 5G systems. They are also being considered as error correcting codes in memory systems.
Polar codes can be encoded and decoded with relatively low complexity, where the encoding complexity of polar codes is N log N for a code of length N. Polar codes are traditionally decoded by a successive cancellation decoder, which can be implemented in a butterfly structure with complexity O(N log N).
Polar codes are based on the concept of channel polarization, which is a technique of applying transformation operations to convert an ensemble of mediocre bit-channels into two disjoint subsets: good channels that have much better reliability (noise-free), and the remaining channels, called bad channels that are transformed into erroneous channels (very noisy). The definition of a bit-channel assumes that a successive cancellation decoder is deployed at the output, where the ith bit-channel, assumes all the preceding i−1 bits are already decoded and are available at channel output, together with all N channel observations for a code of length N, when decoding the ith bit.
A polarization stage includes a channel combining operation and a channel splitting operation. For a 2×2 polarization matrix
      P    =          [                                    1                                0                                                1                                1                              ]        ,this maps 2 bit channels (W, W)→(W−, W+), where W− is referred to as a degraded channel and W+ is referred to as an upgraded channel. With a successive cancellation decoder, and channel output alphabet Y, the following channel transformations W:{0,1}→Y, W−:{0,1}→Y2, and W+:{0,1}→{0,1}×Y2 are generated, as the following inequality in Equation (1) below for the channel information rates holds:I(W−)≤I(W)≤I(W+),  (1)such that the sum capacity is preserved I(W−)+I(W+)=2I(W).
Channel transition probabilities of polarized channels are given by Equations (2) and (3) as follows:
                                                        W              -                        ⁡                          (                                                y                  1                                ,                                                      y                    2                                    |                                      x                    1                                                              )                                =                                    1              2                        ⁢                                          ∑                                                      x                    2                                    ∈                                      {                                          0                      ,                      1                                        }                                                              ⁢                                                W                  ⁡                                      (                                                                  y                        1                                            |                                                                        x                          1                                                ⊕                                                  x                          2                                                                                      )                                                  ⁢                                  W                  ⁡                                      (                                                                  y                        2                                            |                                              x                        2                                                              )                                                                                      ⁢                                  ⁢                  and          ⁢                      :                                              (        2        )                                                      W            +                    ⁡                      (                                          y                1                            ,                              y                                  2                  ,                                            ,                                                x                  1                                |                                  x                  2                                                      )                          =                              1            2                    ⁢                      W            ⁡                          (                                                y                  1                                |                                                      x                    1                                    ⊕                                      x                    2                                                              )                                ⁢                      W            ⁡                          (                                                y                  2                                |                                  x                  2                                            )                                                          (        3        )            such that the successive cancellation decoder decodes x1 with the knowledge of channel observations {y1, y2}, and then decodes x2 with the knowledge of the channel observations as well as the decoded x1. The unreliability of the channel may be measured by a Bhattacharya parameter (BP), Z (W), such that channels with BP close to zero are noiseless channels and channels with BP close to 1 are very noisy.
To construct a polar code of length l, an l×l channel transformation is formed by determining an n-fold Kronecker power of P, where n=log2 l, and an nth Kronecker power is given by
      P    l    =            P              ⊗        n              =                  [                                                            P                                  ⊗                                      (                                          n                      -                      1                                        )                                                                                      0                                                                          P                                  ⊗                                      (                                          n                      -                      1                                        )                                                                                                      P                                  ⊗                                      (                                          n                      -                      1                                        )                                                                                      ]            .      This may also be followed by a bit-reversal permutation. If u1l={u1, u2, . . . , ul} denotes a vector of l independent and uniform binary random variables, then their polar transformation is given by x1l=u1lPl and x1l may be transmitted through l independent copies of a discrete memoryless channel W. In such a case, the BPs of the ith bit channel for a code of length 2l may be calculated recursively from those of a code of length l through the recursive formulas, by denoting the ith bit channel for a code of length l by Wli in Equations (4) and (5) as follows:Z(W2l2i-1)≤2Z(Wli)−Z(Wli)2  (4)Z(W2l2i)=Z(Wli)2  (5)where the equality in Equations (4) and (5) holds in the case of a binary erasure channel.
The channel polarization theorem states that, as the code length N goes to infinity, the bit-channels start polarizing, indicating that they either become good channels, or bad channels. The crux of polar codes is to carry the information bits on the upgraded channels and freeze the degraded channels by setting all bits on degraded channels to a predetermined value, e.g., all zeros. Polar codes are capacity achieving on binary memory-less symmetric channels as the ratio of good channels to the code length N approaches the channel capacity, and as the code length N goes to infinity.